/**
 * 22. 括号生成
 *
 * 【中等】
 *
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 * 示例 1：
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 *
 * 示例 2：
 * 输入：n = 1
 * 输出：["()"]
 */

function generateParenthesis(n: number): string[] {
	const ans: string[] = []

	_generate(0, 0, n, '')

	return ans

	function _generate(left, right, n, s) {
		if (left === n && right === n) {
			ans.push(s)
		}

		if (left < n) {
			_generate(left + 1, right, n, s + '(')
		}
		if (right < left && right < n) {
			_generate(left, right + 1, n, s + ')')
		}
	}
}
